package com.jeff.practice;

import java.util.PriorityQueue;

public class KthLargestElementHeap {

    public static void main(String[] args) {
        int[] nums = {3, 2, 1, 5, 6, 4};
        int k = 2;
        System.out.println(findKthLargest(nums, k)); // 输出: 5
    }

    public static int findKthLargest(int[] nums, int k) {
        // 使用最小堆
        PriorityQueue<Integer> minHeap = new PriorityQueue<>(k);

        // 构建一个大小为 k 的最小堆 堆顶元素就是第K大的元素
        for (int num : nums) {
            minHeap.offer(num);
            // 如果堆的大小大于 k，则删除堆顶元素，保持堆的大小为 k 最后留下来的就是 第 k 大的元素
            if (minHeap.size() > k) {
                minHeap.poll();
            }
        }

        // 堆顶元素就是第 k 个最大的元素
        return minHeap.peek();
    }
}
